In 1972, Woodall raised the following Ore type condition for directedHamilton cycles in digraphs: Let $D$ be a digraph. If for every vertex pair $u$and $v$, where there is no arc from $u$ to $v$, we have $d^+u)+d^-(v)\geq |D|$,then $D$ has a directed Hamilton cycle. By a correspondence between bipartitegraphs and digraphs, the above result is equivalent to the following result ofLas Vergnas: Let $G = (B,W)$ be a balanced bipartite graph. If for any $b \inB$ and $w \in W$, where $b$ and $w$ are nonadjacent, we have $d(w)+d(b) \geq|G|/2 + 1$, then every perfect matching of $G$ is contained in a Hamiltoncycle. The lower bounds in both results are tight. In this paper, we reduce bothbounds by $1$, and prove that the conclusions still hold, with only a fewexceptional cases that can be clearly characterized.
展开▼
机译：1972年，Woodall在有向图中提出了定向汉密尔顿循环的下列矿石类型条件：设$ D $为有向图。如果对于每个顶点对$ u $和$ v $，从$ u $到$ v $没有弧，我们有$ d ^ + u）+ d ^-（v）\ geq | D | $，则$ D $具有定向汉密尔顿周期。通过二部图和二部图之间的对应关系，上述结果等同于Las Vergnas的以下结果：令$ G =（B，W）$是平衡的二部图。如果对于任何$ b \ inB $和$ w \ in W $，其中$ b $和$ w $不相邻，我们有$ d（w）+ d（b）\ geq | G | / 2 + 1 $，那么每个$ G $的完美匹配都包含在汉密尔顿周期中。两种结果的下限都很严格。在本文中，我们将两个边界都减少了1美元，并证明了结论仍然成立，只有少数例外情况可以清楚地描述。
展开▼
